Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра прикладної математики КУРСОВА РОБОТА з курсу “Дискретна математика” на тему: “Алгебра предикатів. Квантори. Означення. Операції. ” Зміст Вступ Поняття предиката Логiка предикатiв Квантори Формули логіки предикатів Рівносильність формул Здійснюваність. Загальнозначущість. Література Анотація Вступ Алгебра висловлювань i як формальна (аксiоматична) теорiя, є важливою i невiд’ємною складовою частиною всiх числень математичної логiки. Однак вона є занадто бiдною для опису та аналiзу найпростiших логiчних міркувань. Однiєю з причин цього є те, що у численнi висловлювань будь-яке просте висловлення розглядається як вихiдний об’єкт дослiдження, неподiльне цiле, позбавлене частин i внутрiшньої структури, яке має лише одну властивiсть - бути або iстинним, або хибним. Для того, щоб побудувати систему правил, яка дозволяла б проводити логiчнi мiркування для виведення нетривiальних правильних висновкiв з урахуванням будови i змiсту простих висловлень, використовується формальна теорiя, що дiстала назву числення предикатiв. Якщо числення висловлювань дає змогу доводити теореми для внутрішніх потреб логіки, то числення предикатів забезпечує можливість описувати й доводити теореми для конкретних розділів математики. Логіка предикатів дає змогу формулювати співвідношення між елементами реального світу і виводити подібні відношення або теореми в математиці. Числення висловлювань – досить вузька логічна система. Існують, наприклад, такі типи логічних міркувань, які не можуть бути здійснені в межах логіки висловлювань: Кожний друг Івана є другом Петра. Сидір не є другом Івана. Отже, Сидір не є другом Петра. Просте число два – парне. Отже існують прості парні числа. Коректність цих висновків грунтується на внутрішній структурі самих речень і значень слів “кожний” та “існують”. Існують такі види логічних формул, які не можна записати у вигляді формул числення висловлювань. Наприклад: Всі риби, окрім акул, добре відносяться до дітей; Всі люди смертні. Сократ – людина. Значить Сократ смертний. Коректність таких висновків грунтується не тільки на істиності відповідних функціональних відношень, а також і на розумінні таких слів, як “всі”, “всякий” і т.д. Для того щоб зробити більш зрозумілою структуру складних висловлювань, користуються спеціальною мовою – мовою числення предикатів першого порядку. 1.Поняття предиката Теорiя предикатiв починається з аналiзу граматичної будови простих висловлювань i грунтується на такому висновку: простi висловлювання виражають той факт, що деякi об’єкти (або окремий об’єкт) мають певнi властивостi, або що цi об’єкти знаходяться мiж собою у певному вiдношеннi. Наприклад, в iстинному висловлюванні «3 є просте число» пiдмет «3» - це об’єкт, а присудок «є просте число» виражає деяку його властивiсть. У латинськiй граматицi присудок називається предикатом, звiдси цей термiн i увiйшов у математичну логiку. Головним для логiки предикатiв є саме друга складова речення-висловлення - присудок-властивiсть. Вона фiксується, а значення об’єкта пропонується змiнювати так, щоб кожен раз отримувати осмисленi речення, тобто висловлення. Розглянемо речення, що залежить від параметрів, наприклад «х – парне число», «х менше у», «х + у = z», «х – батько у», «х та у – брати» тощо. Якщо х, у, z у перших трьох реченнях замінити деякими числами, то матимемо певні висловлення, які можуть бути істинними або хибними. Наприклад, «3 – парне число», «2 менше 5», «3 + 2 = 7». Останні два речення виражають родинні відносини між членами сім’ї і перетворюються на певні висловлення, істинні або хибні, при заміні х та у іменами членів сім’ї: «Іван – батько Петра», «Іван і Олег брати». Речення такого типу називаються предикатами. Точніше предикатом Р(х1,...,хn) називається функція, змінні якої набувають значень із деякої множини М, а сама вона набуває двох значень: 1 (істинне) і 0 (хибне), тобто Р(х1,...,хn): Мn → {1, 0}. Множина M називається предметною о...